TIS Chapter 5
Multiversion Scheduleについて．
これまではSingle Versionのデータベースにおけるトランザクションを議論してきた．
すなわち$ w_i(x)は書込み命令であり，過去の$ xの値を上書きするものだった．
議論の前フリとして，以下を置く
無限のリソースがあるので無限のバージョンが持てる．
バージョンは transparentである．
すなわち，ユーザやアプリからはバージョンの概念が見えない．
このバージョンを読む，という風にreadの引数を増やすことはできない．
なぜこの仮定を置くかというと，トランザクションのセマンティクスを維持したいから．
並列性を上げて並行実行になっても直列実行と transparentであることがTxの意義．
その特性を保ったまま，multiversionizeするとどうなるか，という議論をここではする．
であるから「過去のバージョンが明に読める」という機能とは直交する議論となる．
以下店入メモ
p190難しい．
monoversion scheduleはmultiversion scheduleの1パターンにすぎない.
全てのread stepが最後のwrite stepの結果を読むとそうなる
つまり$ r_1(h(x)) = r_1(x0)みたいな感じのバージョン関数$ hを定義することを前提にしている
MVの場合CSRのグラフ検証があまり適していない
$ s = w_1(x)c_1 r_2(x)w_2(y)c_2というmonoversion serial historyがあるとする
$ m = w_1(x1)c_1 r_2(x0)w_2(y2)c_2というmultiversion historyがあるとする
両者serial historyだが $ sは $ T1 \to T2で$ mはその逆．
バージョンという概念抜きで見るとsとmは同じスケジュールなので，同じ依存関係グラフを生成してしまう
がreads-from関係はまるで違う.
頼みのツナはやはりRF．
RF比較のmonoversionとの違いは以下
最後のwriteの結果がどうという話，すなわちalive/deadはもはや関係ない
全バージョン常に参照可能であるため
ようするにバージョン関数$ hの結果だけが重要．
serial multiversion scheduleとmultiversion scheduleを比較してview equivalentかどうか検査する，と考える
これは充分ではない．
$ m = r_1(x_0)r_1(y_0)w_1(x_1)w_1(y_1)c_1r_2(x_0)r_2(y_1)c_2
$ s = r_1(x)r_1(y)w_1(x)w_1(y)c_1r_2(x)r_2(y)c_2
両方serial scheduleだけど添字があることによって意味が変わってくる
さっきもこの話したな．．．
serial monoversion scheduleをserial multiversion scheduleにcastすればよい
さて，こうするとやっぱりVSRの証明と同じでNP completeである
MVSRはMonoversion VSRと異なりGraph-theoreticに説明できる
依存関係グラフはCSRの特権ではない
CSRの依存関係グラフと異なる点がある
conflictはw-rのみを検証すればよい
すごいシンプルに $ t_i \to t_j かつ $ r_j(x_i)だけ見ればよい
View Equivalentならグラフが同じであるが，この逆は成り立たない．
依存関係グラフが同じでもバージョンが違うから．
またその話か．．．
MVSRの依存関係グラフのためにはversion orderという考え方を導入する
これはwriteのexecution orderとは直交する．
x1 x0 x3 x2 の順番で書かれたので 1 <<0 << 3<< 2 のような感じ，ではない．
論理的なバージョン順序のことを指す．
これ以上の説明はないッ
w-w conflictでエッジを引くのではなくversion orderでエッジを引くと 先の問題に対処できる
$ w_i(x)r_j(x)w_k(x)があるとする．iとjがコミット済みだとする．
$ kはこの位置でもいいし$ k < iにもできる．これがversion orderの力．
トポロジカルソート可能ならtotal order生成可能というところはCSRと同一のロジック
以下引用で例を見てみる
So for each triple of operations wj(xj), rk(xj), and wi(xi) on the same data item x,
the MVSG contains two out of the three potential edges.
An edge from Tj -> Tk is always present.
で，もうひとつのedgeは，2パターン.
まず，
if the version order is xi < xj, meaning that in an equivalent monoversion schedule
wi(xi) would precede wj(xj)
つまり $ T_i \to T_j \to T_k
次に，
if the version order is xj < xi, so that wi(xi) would follow wj(xj)...
これは $ T_k \to T_i が確定
なんと$ T_j \to T_iではない!
monoversion scheduleとequivalentであるためには，$ r_k(x_j)をどう考えるかが重要
monoversion scheduleはmost recent versionを読むという縛りがあることを思い出そう
なので$ w_j(x_j)\to r_k(x_j) \to w_i(x_i)なのです
ここで重要なDefinition5.8
For a given schedule $ mand a version order $ <<, the multiversion serialization graph MVSG(m, <<) of $ m then is the conflict graph $ G(m) == (V,E)with the following edges added for each $ r_k(x_j) and$ w_i(x_i)in CP(m), where $ k, i, j are pairwise distinct: if $ x_i << x_j, then $ (t_i, t_j) \ni E, otherwise $ (t_k, t_i) \ni E
さきほどの引用例と同じで，ようするにversion orderによってedgeが変わるということ．
かなりcounter-intuitiveだな...
ちょっと休憩．
さて，MVSRのグラフについて考える．
If a multiversion history happens to have an acyclic conflict graph,
we can apply topological sorting to obtain a total order or ,equivalently, a serial multiversion history;
例によってグラフを描いてトポロジカルソートできるか調べるという手法を考える．
で，まずこのやり方がserial multiversion historyについて正しいかを考える必要がある．
もしserial multiversion historyから生成したconflict graphが全てacyclicなら，逆にこれはプロトコルに使えるというわけ．
multiversion historyをmonoversion historyにcastする(つまり添字を消す)とreads-fromが変わることはさんざん言った．
このためナイーブにview equivalentかどうかを検証しても意味がない.
ところがversion orderをedgeに導入すればこの問題を解決できる．
つまり$ r-wと$ Version Orderをedgeとしたグラフを描けばいい．
これがMultiversion Serialization Graph(MVSG).
では証明．
もし$ MVSG(m, VersionOrder)がacyclicなら，topo-sortした結果serial historyになる．
topo-sortした結果の$ m'とmはView-Equivalentであるはず．
さて，$ r_k(x_j) と $ w_i(x_i)があるとする
Version Orderによって以下になる(さっきのDef 5.8と同じ)
1.$ x_i < x_jなら $ T_i \to T_j
2.$ x_j < x_iなら $ T_k \to T_iがある
この定義から，MVSGにおいて$ T_jと$ T_kとの間に$ w_i(x)となる$ T_iは必ず存在しない．
つまり，MVSGにおいて，version orderとr-wの2 typeのedgeだけで全てのwriteを検証することができる．
よって，あるedgeの間に他のwriteが実は挟まっていた，ということは起こらない．
よって，MVSGからはversion number(≠ version order)を除外してもRFは変わらない
おーやべーワカンネー
以下考察
CSR的なgraphからversion numberを除外するとRFが変わるのはさんざんやった
しかしr-wとVersion numberだけのgraphを用意すると，これは変わらないと言っている
で，$ mからversion numberを除外したスケジュールを$ mとする．
numberを除外しただけでversion orderはちゃんとある
あるスケジュール $ MV(m, <<)からversion edgeだけを抜き出したものを考える
Sinse version order edges depend only on the operations in $ m and the version order,
but not on the sequencing of the operations in $ m,
we can conclude that if $ m and $ m' are multiversion histories such that $ trans(m) = trans(m')
then $ MV(m, <<) = MV(m', <<) for every version order <<.
sequencingて何だよ...
これは，$ mにおける命令列の順序とversion orderは関係ないということ．
まあversion orderの定義からしてそうだ．
version numberをdropしても生成されるMVSGのedgeは変わらないと言っている．
で，$ mがMVSRなら，version numberをdropした$ m'はserial monoversion historyだよね?という話になる
うおーやっと分かった．頭いいな・・・
View Equivalentすなわち$ m =_v m'であることは既にわかっている
既に見た通りVersion Orderが同じなら $ MV(m, <<) = MV(m', <<)である．
つまり$ G(m) = G(m')
そして$ m'はserialなので$ G(m')はacyclic
え，いつその証明した？
全然わからないのでp189からもう1回追い直す．